package TOP101;

/**
 * @Question BM3
 * @Date 2022/11/1 22:11
 * @Solution
 */
public class BM3 {
    public ListNode reverseOne (ListNode head, int m, int n) {
        if (head == null) {
            return null;
        }
        if (head.next == null || m == n) {
            return head;
        }
        // 找到连接点m-2
        ListNode linkHead = null;
        if (m != 1) {
            linkHead = head;
            for (int i = 1; i < m - 1; i++) {
                linkHead = linkHead.next;
            }
        }
        // 找到连接点尾部n+1
        ListNode linkTail = head;
        for (int i = 0; i < n; i++) {
            linkTail = linkTail.next;
        }
        //反转部分链表
        ListNode cur = head;
        for (int i = 1; i < m; i++) {
            cur = cur.next;
        }
        ListNode t = new ListNode(cur.val);
        cur = cur.next;
        for (int i = 0; i < n - m; i++) {
            ListNode ne = new ListNode(cur.val);
            ne.next = t;
            t = ne;
            cur = cur.next;
        }
        //拼接
        if (linkHead != null) {
            linkHead.next = t;
        }
        if (linkTail != null) {
            cur = t;
            while (cur.next != null) {
                cur = cur.next;
            }
            cur.next = linkTail;
        }
        if (linkHead == null) {
            return t;
        } else if (linkTail == null) {
            return head;
        }
        return head;
    }
    public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        ListNode cur = head;
        int len = 0;
        while (cur != null) {
            len++;
            cur = cur.next;
        }
        int m = 1;
        int n = k;
        while (n <= len) {
            head = reverseOne(head, m, n);
            m = n + 1;
            n += k;
        }
        return head;
    }
}
